package leetcode_ago.top_k;
/**
 * 题目：查找和最小的k个数对（pair:数对）
 * 给定两个以升序排列的整数数组nums1和nums2 ,以及一个整数 k 。定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。
 * 请找到和最小的k个数对(u1,v1),(u2,v2)...(uk,vk)
 * 1 <= nums1.length, nums2.length <= 105
 * -109 <= nums1[i], nums2[i] <= 109
 * nums1 和 nums2 均为升序排列
 * 1 <= k <= 1000
 */
import java.util.*;

/**
 * 分析：
 * 1.和最小的k个数对，topk，用类存储数组中元素，应用到最大堆
 * 2.数对k值可能大于数组长度，如[1,2],[1],k=3,此时只能出2个，没有第三个可以出，所以引出相关遍历条件：
 * 1）遍历nums1，nums2时循环结束条件：Math.min(nums.length,k);
 * k大于数组长度时遍历到数组长度即可，k小于数组长度时遍历到k即可，因为后面的数值随着升序也是增大的，用不上
 * 2）最终出队时，队内元素可知可能不够k个，所以循环条件是：<k&&!queue.isEmpty()
 */
public class Num373_KSmallestPairs1 {
    private class Pairs{
        int x;//数组1中元素
        int y;//数组2中元素
        public Pairs(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        //1.构建最大堆
        Queue<Pairs> queue=new PriorityQueue<>(new Comparator<Pairs>() {
            //（一般和越小越排在前面，返回值越小，jdk默认最小堆，返回值越小越先出队
            // 所以和越小越先出队，现在要用最大堆的输出，和小反而不出堆【返回值小（和大）先出队，即大的元素先出，改为最大堆输出了】）
            @Override
            public int compare(Pairs o1, Pairs o2) {
                return (o2.x+o2.y)-(o1.x+o1.y);
            }
        });
        //2.遍历两个数组
        for (int i = 0; i < Math.min(nums1.length, k); i++) {
            for (int j = 0; j < Math.min(nums2.length, k); j++) {
                if(queue.size()<k){
                    queue.offer(new Pairs(nums1[i],nums2[j]));
                }else{
                    Pairs pair=queue.peek();
                    if(nums1[i]+nums2[j]> pair.x+ pair.y){
                        continue;
                    }else{
                        queue.poll();
                        queue.offer(new Pairs(nums1[i],nums2[j]));
                    }
                }
            }
        }
        //此时堆内存储好了和最小的元素对
        List<List<Integer>> ret=new ArrayList<>();
        for (int i = 0; i < k && (!queue.isEmpty()); i++) {
            List<Integer> temp=new ArrayList<>();
            Pairs pair=queue.poll();
            temp.add(pair.x);
            temp.add(pair.y);
            ret.add(temp);
        }
        return ret;
    }
}
